from ConvexHull import ConvexHull   
import numpy as np
import math


class Polygon(object):
    '''
    Polygon class is a detector of two overlapped polygons. 
    '''

    def __init__(self, pts):
        '''
        Constructor
        '''
        self.points = np.array(ConvexHull.convex_hull(np.array(pts)))
        self.edges = []
        
        for i in range(len(self.points)):
            p = self.points[i]
            if i == len(self.points)-1:
                q = self.points[0]
            else:
                q = self.points[i+1]
            self.edges.append(q-p)
        self.edges = np.array(self.edges)
         
        
    def collidepoly(self, otherpoly):
        # iterate over self edges => edge
            # for each edge, find perpendicular line to that edge => axis
            # project self to axis => self projection (min,max)
            # project other to axis => other projection
            # if separation, return False
        # (gone through the loop), return True
        
        for edge in np.vstack((self.edges,otherpoly.edges)):
            unitedge = self.normalize(edge)
            axis = self.perpendicular(unitedge)
            selfprojection = self.project(axis)
            otherprojection = otherpoly.project(axis)
            if selfprojection[1] < otherprojection[0]:
                return False
            elif selfprojection[0] > otherprojection[1]:
                return False    
            
        return True
    
    
    def project(self, axis):
        unitaxis = self.normalize(axis)
        projectedpts = []
        for vertex in self.points:
            projectpt = self.dot(unitaxis, vertex)
            projectedpts.append(projectpt)
        
        return (min(projectedpts), max(projectedpts))
    
    
    def perpendicular(self, v):
        return np.array([-v[1], v[0]])
    
    def magnitude(self, v):
        return math.sqrt(sum(v[i]*v[i] for i in range(len(v))))


    def normalize(self, v):
        vmag = self.magnitude(v)
        return v if vmag == 0.0 else np.array([v[i] / vmag  for i in range(len(v))])

    def dot(self, u, v):
        return sum(u[i]*v[i] for i in range(len(u)))




if __name__ == "__main__":
    points = [(0,0),(0,20),(20,18)]
    poly = Polygon(points)
    
    points1 = [(0,5),(20,3),(23,0)]  # collide case
    poly1 = Polygon(points1)
    
    points2 = [(20,15),(30,12),(28,3),(15,0)]   # not collide
    poly2 = Polygon(points2)
    
    points3 = [(400,0),(460,0),(460,90),(400,90)]
    poly3 = Polygon(points3)
    
    topsidewalk = Polygon(2*np.array([(0,248), (244,0), (0,294), (285,0)]))         # top sidewalk
    bottomsidewalk = Polygon(2*np.array([(525,0), (109,540), (605,0), (365,540)]))  # bottom sidewalk
    
    
    print poly3.collidepoly(bottomsidewalk)
    
        
        